package com.hydra.base.tree;


import org.jsoup.internal.StringUtil;
import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.*;

/**
 * 树化工具
 *
 */
public class TreeUtils {

    /**
     * 树化
     * @param treeNodes 扁平节点数据
     * @return 树化的节点列表（列表中每一节点都是一棵树）
     */
    public static <T extends TreeNode<T>> List<T> treeing(List<T> treeNodes) {
        Map<String, T> nodeMap = new HashMap<>(treeNodes.size());
        treeNodes.forEach(t -> nodeMap.put(t.getCode(), t));

        List<T> result = new ArrayList<>();
        for (T treeNode : treeNodes) {
            T parent = nodeMap.get(treeNode.getParentCode());
            if (parent != null) {
                //判断是否存在节点死循环的情况
                if(!isDeadCycle(nodeMap, parent, treeNode.getCode())){
                    parent.getChildren().add(treeNode);
                    continue;
                }
            }
            // 仅添加顶层节点
            result.add(treeNode);
        }

        return result;
    }

    /**
     * 判断树节点是否存在死循环的情况
     */
    private static <T extends TreeNode<T>> boolean isDeadCycle(Map<String, T> nodeMap, T parent, String code){
        if(StringUtil.isBlank(code) || parent == null){
            return false;
        }
        String parentCode = parent.getParentCode();
        if(code.equals(parentCode)){
            return true;
        }
        T p = nodeMap.get(parentCode);
        return isDeadCycle(nodeMap, p, code);
    }

    /**
     * 扁平化
     * @param treeNodes 树化数据
     * @return 扁平数据
     */
    public static <T extends TreeNode<T>> List<T> flattening(List<T> treeNodes) {
        if (!CollectionUtils.isEmpty(treeNodes)) {
            return new ArrayList<>();
        }
        List<T> newList = new LinkedList<>();
        Queue<T> queue = new LinkedList<>(treeNodes);
        while (!queue.isEmpty()) {
            T pollMenuBar = queue.poll();
            List<T> children = pollMenuBar.getChildren();
            if (!CollectionUtils.isEmpty(children)) {
                queue.addAll(children);
            }
            newList.add(pollMenuBar);
        }
        return newList;
    }
}